//**********************************************************************
//	Programmer	-	Sujal Bista
//	File Name	-	modelQuick.h
//	Description	:	
//					quick 3d model handler
//
//**********************************************************************

#ifndef _MODEL_QUICK_H
#define _MODEL_QUICK_H

#pragma once

#include "global.h"
#include "dataTypes.h"
#include "graphicsUtility.h"
#include "bucketList.h"
#include "camera.h"
#include <iostream>
#include <fstream>
class model;

class modelQuick
{
		#define MAX_FILE_NAME 128
		#define MAX_NAME 128
		#define MAXIMUM_MATRIX_COUNT 12
		#define MAXIMUM_BONE_PER_VERTEX_INFLUENCE_COUNT 4

	public:

		//mesh data
		class meshData
		{
			public:
				//vertex data
				class vertexData
				{
					public:
						float3 position;
						float3 normal;
						float3 tangent;
						float2 texCoord;
						
						friend std::ostream& operator<<(std::ostream &out, const vertexData& vData)
						{
							out<<vData.position<<", "<<vData.normal<<", "<<vData.tangent<<", "<<vData.texCoord<<std::endl;
							return out;
						}
				};
				//each face can have separate material
				class faceData
				{
					public:
						uint3 vertexIndex;
						uint3 adjacency;
						unsigned int materialIndex;
				};
				//material data
				class materialData
				{
					public:
						float4 diffuse;  //diffuse color	
						float3 ambient;  //ambient color
						float3 specular; //specular color
						float3 emissive; //emissive color
						float power;	//specular highlight power
						char fileName[MAX_FILE_NAME];						
						union
						{
							shaderResourceView *textureSRV;
							UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
						};
						union
						{
							samplerState  *textureSampler;
							UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
						};
				};

				char name[MAX_NAME];
				unsigned int vertexCount;
				unsigned int faceCount;				
				unsigned int materialCount;
				union
				{
					vertexData *vertices;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					faceData *faces;
					UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					materialData *materials;
					UINT64 _forceSpace64_2;			//Force the union to 64bits. DX SDK trick
				};				
		};
		//animation sets
		class animationData
		{
			public:
				//per bone animation data
				class boneAnimationData
				{
					public:

						struct floatQuaternionKey
						{
							float time;
							floatQuaternion value;
						};

						struct float3SKey
						{
							float time;
							float3 value;
						};
						
						char name[MAX_NAME];
						unsigned int rotationCount;
						unsigned int scaleCount;
						unsigned int translationCount;
						
						union
						{
							floatQuaternionKey *rotations;
							UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
						};
						union
						{
							float3SKey *scales;
							UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
						};
						union
						{
							float3SKey *translations;
							UINT64 _forceSpace64_2;			//Force the union to 64bits. DX SDK trick
						};
				};
				
				char name[MAX_NAME];

				//number of 
				unsigned int boneAnimationCount;
				//number of ticks per second
				float ticksPerSecond;
				//bone Animation data

				union
				{
					boneAnimationData *boneAnimations;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
		};				
		//contains information about skinning
		class skinData
		{
			public:
				//bone data
				class boneData
				{
					public:
						char name[MAX_NAME];
						float4x4 offsetMatrix;
						unsigned int boneHierarchyIndex;	//index of the associated boneHierarchy in the array
						unsigned int influenceCount;

						union
						{
							unsigned int *vertexIndex;
							UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
						};

						union
						{
							float *weights;
							UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
						};
				};

				//bone hierarchy
				class boneHierarchyData
				{
					public:
						char name[MAX_NAME];
						float4x4 transformationMatrix;
						unsigned int siblingIndex;
						unsigned int childIndex;
						unsigned int boneIndex;	//index of the associated bone in the array
						unsigned int boneHierarchyIndex; //index of bone hierarchy index in the array

						//traverses breadth first
						void traverseBFS(boneHierarchyData *bonesHierarchy, bucketList<boneHierarchyData *> &tree)
						{
							//add the data to the list
							tree.addBack(this);
							if(siblingIndex!=(unsigned int)-1)
								bonesHierarchy[siblingIndex].traverseBFS(bonesHierarchy,tree);
							if(childIndex!=(unsigned int)-1)
								bonesHierarchy[childIndex].traverseBFS(bonesHierarchy,tree);
						}
				};

				//number of bones
				unsigned int boneCount;
				//number of boneHierarchy
				unsigned int boneHierarchyCount;
				
				union
				{
					boneData *bones;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					boneHierarchyData *bonesHierarchy;
					UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
				};
				unsigned int rootIndex;

			private:

				//searches for a bone from the list
				unsigned int findBone(const char *name)
				{
					if(name)
					{
						for(unsigned int i=0;i<boneCount;i++)
						{
							if(bones[i].name && strcmp(bones[i].name,name)==0)
								return i;
						}
					}
					return (unsigned int)-1;
				}

			public:

				//initializes the skin
				void initialize(void)
				{
					for(unsigned int i=0;i<boneHierarchyCount;i++)
					{
						bonesHierarchy[i].boneHierarchyIndex=i;
						bonesHierarchy[i].boneIndex=findBone(bonesHierarchy[i].name);
						if(bonesHierarchy[i].boneIndex!=(unsigned int)-1)
							bones[bonesHierarchy[i].boneIndex].boneHierarchyIndex=i;
					}
				}

				//searches for a bone from the hierarchy list
				unsigned int findHierarchyBone(const char *name)
				{
					if(name)
					{
						for(unsigned int i=0;i<boneHierarchyCount;i++)
						{
							if(bonesHierarchy[i].name && strcmp(bonesHierarchy[i].name,name)==0)
								return i;
						}
					}
					return (unsigned int)-1;
				}
		};
		//different instances of the mesh
		class instanceData
		{
			public:

				//face group is group of faces that share common characterstics
				class faceGroupData
				{
					public:

						unsigned int materialIndex;
						unsigned int faceIndexCount;
						unsigned int boneIncluenceCount;

						//indices and count of the faces in the group
						union
						{
							unsigned int *faceIndices;
							UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
						};
										
						//indices and count of the bones used in the group
						union
						{
							unsigned int *boneIndices;
							UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
						};				

						faceGroupData(void)
						{
							materialIndex=0;

							faceIndices=NULL;
							faceIndexCount=0;
				
							boneIncluenceCount=0;
							boneIndices=NULL;
						}

						//copy constructor
						faceGroupData(const faceGroupData &data)
						{
							materialIndex=data.materialIndex;
							faceIndexCount=data.faceIndexCount;
							boneIncluenceCount=data.boneIncluenceCount;
					
							if(faceIndexCount)
							{
								faceIndices=new unsigned int[faceIndexCount];
								memcpy(faceIndices,data.faceIndices,sizeof(unsigned int)*faceIndexCount);
							}
							else
								faceIndices=NULL;

							if(boneIncluenceCount)
							{
								boneIndices=new unsigned int[boneIncluenceCount];
								memcpy(boneIndices,data.boneIndices,sizeof(unsigned int)*boneIncluenceCount);
							}
							else
								boneIndices=NULL;
			
						}

						//assignment operator
						faceGroupData& operator=(const faceGroupData& data)
						{
							if(this!=&data)
							{
								clear();
								materialIndex=data.materialIndex;
								faceIndexCount=data.faceIndexCount;
								boneIncluenceCount=data.boneIncluenceCount;
						
								if(faceIndexCount)
								{
									faceIndices=new unsigned int[faceIndexCount];
									memcpy(faceIndices,data.faceIndices,sizeof(unsigned int)*faceIndexCount);
								}

								if(boneIncluenceCount)
								{
									boneIndices=new unsigned int[boneIncluenceCount];
									memcpy(boneIndices,data.boneIndices,sizeof(unsigned int)*boneIncluenceCount);
								}
							}
							return *this;
						}

						//free data
						void clear(void)
						{
							delete[] faceIndices;
							delete[] boneIndices;

							materialIndex=0;

							faceIndices=NULL;
							faceIndexCount=0;
				
							boneIncluenceCount=0;
							boneIndices=NULL;
						}

						~faceGroupData()
						{
							clear();
						}
				};

				//translation matrix
				float4x4 translationMatrix;

				//time passed
				float timePassed;

				//subset of indices of bones that effect a vertex
				union
				{
					unsigned int *boneIndicesPerVertex;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				//weight of each bone that effect a vertex
				union
				{
					float *boneWeightsPerVertex;
					UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
				};
				//pointer to the mesh
				union
				{
					meshData *meshPtr;
					UINT64 _forceSpace64_2;			//Force the union to 64bits. DX SDK trick
				};
				//pointer to the skin
				union
				{
					skinData *skinPtr;
					UINT64 _forceSpace64_3;			//Force the union to 64bits. DX SDK trick
				};
				//pointer to the animation
				union
				{
					animationData *animationPtr;
					UINT64 _forceSpace64_4;			//Force the union to 64bits. DX SDK trick
				};
				//saves the index of bone hierarcy for each animation data
				union
				{
					unsigned int *animationBoneHierarchyConnector;
					UINT64 _forceSpace64_5;			//Force the union to 64bits. DX SDK trick
				};
				//matrices used for this instance
				union
				{
					float4x4 *transformationMatrices;
					UINT64 _forceSpace64_6;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					float4x4 *combinedTransformationMatrices;
					UINT64 _forceSpace64_7;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					float4x4 *finalMatrices;
					UINT64 _forceSpace64_8;			//Force the union to 64bits. DX SDK trick
				};

				//position in current instance
				union
				{
					unsigned int *rotationKeyIndices;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					unsigned int *translationKeyIndices;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				union
				{
					unsigned int *scaleKeyIndices;
					UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
				};
				//group of face that share common characterstics
				bucketList<faceGroupData> faceGroups;

			private:
				//updates the matrices
				void updateHierarchy(skinData::boneHierarchyData *bonesHierarchy, unsigned int currBoneHierarchyIndex,float4x4 *parentMatrix)
				{
					skinData::boneHierarchyData &currBoneHierarchy=bonesHierarchy[currBoneHierarchyIndex];

					if(parentMatrix==NULL)
						combinedTransformationMatrices[currBoneHierarchyIndex]=transformationMatrices[currBoneHierarchyIndex];
					else
						combinedTransformationMatrices[currBoneHierarchyIndex]=transformationMatrices[currBoneHierarchyIndex]*(*parentMatrix);

					if(currBoneHierarchy.siblingIndex!=(unsigned int)-1)
						updateHierarchy(bonesHierarchy,currBoneHierarchy.siblingIndex,parentMatrix);

					if(currBoneHierarchy.childIndex!=(unsigned int)-1)
						updateHierarchy(bonesHierarchy,currBoneHierarchy.childIndex,&combinedTransformationMatrices[currBoneHierarchyIndex]);
				}

				//arranges mesh into groups
				void computeFaceGroups(unsigned int maximumMatrixCount,unsigned int maximumBoneInfluenceCount)
				{
					//clear the existing group
					faceGroups.clear();
					//faceGroup *currentGroup;

					//returns the best bone to use for the face
					bool *faceAdded=new bool[meshPtr->faceCount];
					memset(faceAdded,0,sizeof(bool)*meshPtr->faceCount);

					if(skinPtr)
					{
						//calculate the copy size
						maximumMatrixCount=MIN(maximumMatrixCount,skinPtr->boneCount);
						maximumBoneInfluenceCount=MIN(maximumBoneInfluenceCount,skinPtr->boneCount);

						if(!skinPtr->boneCount)
							goto EXIT;

						delete[] boneIndicesPerVertex;
						delete[] boneWeightsPerVertex;	
						//returns the best bone to use for each vertices
						findBestBoneVertices(maximumBoneInfluenceCount,boneIndicesPerVertex,boneWeightsPerVertex);

						for(unsigned int i=0;i<meshPtr->materialCount;i++)
						{
							unsigned int startFaceIndex=0;
							do
							{
								bucketList<unsigned int> groupBoneIndices;	//bone indices valid
								bucketList<unsigned int> faceIndices;

								bool firstInterval=false;
								for(unsigned int j=startFaceIndex;j<meshPtr->faceCount;j++)
								{
									if(!faceAdded[j])
									{
										if(meshPtr->faces[j].materialIndex==i)
										{	
											if(addFaceToGroup(j,groupBoneIndices,maximumMatrixCount,maximumBoneInfluenceCount,boneIndicesPerVertex))
											{
												faceIndices.addBack(j);
												faceAdded[j]=true;
											}
											else
											{
												if(!firstInterval)
												{
													startFaceIndex=j;
													firstInterval=true;
												}
											}					
										}
									}
									else
									{
										if(!firstInterval)
											startFaceIndex=j+1;
									}
								}
								//make a mesh group
								if(faceIndices.size())
								{
									faceGroupData tempGroup;
									faceGroups.addBack(tempGroup);
		
									faceGroupData &currentGroup=faceGroups[faceGroups.size()-1];

									//copy the data
									currentGroup.materialIndex=i;

									currentGroup.faceIndexCount=faceIndices.size();
									currentGroup.faceIndices=new unsigned int[currentGroup.faceIndexCount];
									//copy indices of the face
				
									for(unsigned int l=0;l<faceIndices.size();l++)
										currentGroup.faceIndices[l]=faceIndices[l];						

									currentGroup.boneIncluenceCount=(unsigned int)groupBoneIndices.size();
									currentGroup.boneIndices=new unsigned int[currentGroup.boneIncluenceCount];
									//copy indices of the bone
									for(unsigned int k=0;k<groupBoneIndices.size();k++)
										currentGroup.boneIndices[k]=groupBoneIndices[k];

								}
								groupBoneIndices.clear();
							}while(startFaceIndex<meshPtr->faceCount);
						}
					}
					else
					{
						for(unsigned int i=0;i<meshPtr->materialCount;i++)
						{
							unsigned int startFaceIndex=0;
							do
							{
								bucketList<unsigned int> faceIndices;

								bool firstInterval=false;
								for(unsigned int j=startFaceIndex;j<meshPtr->faceCount;j++)
								{
									if(!faceAdded[j])
									{
										if(meshPtr->faces[j].materialIndex==i)
										{
											faceIndices.addBack(j);
											faceAdded[j]=true;
										}
									}
									else
									{
										if(!firstInterval)
											startFaceIndex=j+1;
									}
								}
								//make a mesh group
								if(faceIndices.size())
								{
									faceGroupData tempGroup;
									faceGroups.addBack(tempGroup);
		
									faceGroupData &currentGroup=faceGroups[faceGroups.size()-1];
									//currentGroup=faceGroups.addBack();

									//copy the data
									currentGroup.materialIndex=i;

									currentGroup.faceIndexCount=faceIndices.size();
									currentGroup.faceIndices=new unsigned int[currentGroup.faceIndexCount];
									//copy indices of the face
									for(unsigned int l=0;l<faceIndices.size();l++)
										currentGroup.faceIndices[l]=faceIndices[l];
								}
							}while(startFaceIndex<meshPtr->faceCount);
						}
					}
				EXIT:
					delete[] faceAdded;
				}

				//performs partition
				unsigned int partitionKeys(float *data, unsigned int *indices,unsigned int left,unsigned int right,unsigned int pivotIndex)
				{
					float tempF;
					unsigned int tempI;
					float pivotValue = data[pivotIndex];

					SWAP(data[pivotIndex],data[right],tempF);  // Move pivot to end
					SWAP(indices[pivotIndex],indices[right],tempI);  // Move pivot to end

					unsigned int storeIndex = left;
					for(unsigned int i=left;i<right;i++)
					{
						if(data[i] > pivotValue)
						{
							SWAP(data[storeIndex],data[i],tempF);
							SWAP(indices[storeIndex],indices[i],tempI);
							storeIndex++;
						}
					}
					SWAP(data[right],data[storeIndex],tempF); // Move pivot to its final place
					SWAP(indices[right],indices[storeIndex],tempI); // Move pivot to its final place
					return storeIndex;
				}

				//performs quick sort
				void quickSortKeys(float *data, unsigned int *indices,unsigned int left, unsigned int right)
				{
					if(left<right)
					{
						unsigned int pivotIndex = left;

						pivotIndex=partitionKeys(data, indices, left, right, pivotIndex);

						quickSortKeys(data,indices,left,pivotIndex);
						quickSortKeys(data,indices,pivotIndex+1,right);
					}

				}

				//returns the best bone to use for the face
				void findBestBoneVertices(unsigned int maximumBoneInfluenceCount,unsigned int *&boneIndicesPerVertex, float *&boneWeightsPerVertex)
				{
					boneIndicesPerVertex=new unsigned int[meshPtr->vertexCount*maximumBoneInfluenceCount];
					boneWeightsPerVertex=new float[meshPtr->vertexCount*maximumBoneInfluenceCount];

					//go through each vertex
					for(unsigned int i=0;i<meshPtr->vertexCount;i++)
					{
						unsigned int *allBoneIndices=new unsigned int[skinPtr->boneCount];
						float *allBoneWeights=new float[skinPtr->boneCount];

						memset(allBoneWeights,0,sizeof(float)*skinPtr->boneCount);
						//go through each bones
						for(unsigned int j=0;j<skinPtr->boneCount;j++)
						{
							allBoneIndices[j]=j;
							//go through each bone influence
							for(unsigned int k=0;k<skinPtr->bones[j].influenceCount;k++)
							{
								if(skinPtr->bones[j].vertexIndex[k]==i)
								{
									allBoneWeights[j]=skinPtr->bones[j].weights[k];
									break;
								}
							}
						}

						//sort the data
						quickSortKeys(allBoneWeights,allBoneIndices,0,skinPtr->boneCount-1);

						//copy bone indices
						memcpy(&boneIndicesPerVertex[i*maximumBoneInfluenceCount],allBoneIndices,sizeof(unsigned int)*maximumBoneInfluenceCount);

						//normalize the bone weights
						float sum=0;
						for(unsigned int l=0;l<maximumBoneInfluenceCount;l++)
							sum+=allBoneWeights[l]*allBoneWeights[l];
						sum=sqrt(sum);
						if(sum)
						{
							float mult=1.0f/sum;
							for(unsigned int l=0;l<maximumBoneInfluenceCount;l++)
								allBoneWeights[l]*=mult;
			
						}

						memcpy(&boneWeightsPerVertex[i*maximumBoneInfluenceCount],allBoneWeights,sizeof(float)*maximumBoneInfluenceCount);

						delete[] allBoneIndices;
						delete[] allBoneWeights;
					}
				}

				//adds a face to a mesh group
				bool addFaceToGroup(unsigned int &faceIndex,bucketList<unsigned int> &groupBoneIndices,unsigned int maximumMatrixCount,unsigned int maximumBoneInfluenceCount,unsigned int *boneIndices)
				{
					//compute how many indices have to be added for the new face
					bucketList<unsigned int> addedBoneIndices; //indices to be added
					for(unsigned int k=0;k<3;k++)
					{
						unsigned int &vertexIndex=meshPtr->faces[faceIndex].vertexIndex[k];
						for(unsigned int l=0;l<maximumBoneInfluenceCount;l++)
						{
							unsigned int &currBoneIndex=boneIndices[vertexIndex*maximumBoneInfluenceCount+l];
							if(groupBoneIndices.find(currBoneIndex)==NULL && addedBoneIndices.find(currBoneIndex)==NULL)
								addedBoneIndices.addBack(currBoneIndex);
						}
					}

					//check if the cost is resonable
					if(addedBoneIndices.size()+groupBoneIndices.size()<maximumMatrixCount)
					{
						//add the face
						for(unsigned int i=0;i<addedBoneIndices.size();i++)
							groupBoneIndices.addBack(addedBoneIndices[i]);
					}
					else
						return false;
					return true;
				}
			
			public:

				instanceData(void)
				{
					meshPtr=NULL;
					skinPtr=NULL;
					animationPtr=NULL;

					boneIndicesPerVertex=NULL;
					boneWeightsPerVertex=NULL;

					//saves the index of bone hierarcy for each animation data
					animationBoneHierarchyConnector=NULL;

					//time passed
					timePassed=0;

					//matrices used for this instance
					transformationMatrices=NULL;
					combinedTransformationMatrices=NULL;
					finalMatrices=NULL;

					rotationKeyIndices=NULL;
					translationKeyIndices=NULL;
					scaleKeyIndices=NULL;

					translationMatrix.identity();

				}
				
				instanceData(meshData *mPtr,skinData *sPtr,animationData *aPtr,const float4x4 &tMatrix):translationMatrix(tMatrix)
				{
					meshPtr=mPtr;
					skinPtr=sPtr;
					animationPtr=aPtr;

					boneIndicesPerVertex=NULL;
					boneWeightsPerVertex=NULL;

					//saves the index of bone hierarcy for each animation data
					animationBoneHierarchyConnector=NULL;

					//time passed
					timePassed=0;

					//matrices used for this instance
					transformationMatrices=NULL;
					combinedTransformationMatrices=NULL;
					finalMatrices=NULL;

					rotationKeyIndices=NULL;
					translationKeyIndices=NULL;
					scaleKeyIndices=NULL;

				}

				//initializes the instance
				void  initialize(void)
				{
					clear();

					//if the skinning is available perform it
					if(skinPtr)
					{
						animationBoneHierarchyConnector=new unsigned int[animationPtr->boneAnimationCount];

						//matrices used for this instance
						transformationMatrices=new float4x4[skinPtr->boneHierarchyCount];
						combinedTransformationMatrices=new float4x4[skinPtr->boneHierarchyCount];
						finalMatrices=new float4x4[skinPtr->boneHierarchyCount];

						rotationKeyIndices=new unsigned int[skinPtr->boneHierarchyCount];
						translationKeyIndices=new unsigned int[skinPtr->boneHierarchyCount];
						scaleKeyIndices=new unsigned int[skinPtr->boneHierarchyCount];

						//clear the indices
						memset(rotationKeyIndices,0,skinPtr->boneHierarchyCount*sizeof(unsigned int));
						memset(translationKeyIndices,0,skinPtr->boneHierarchyCount*sizeof(unsigned int));
						memset(scaleKeyIndices,0,skinPtr->boneHierarchyCount*sizeof(unsigned int));

						//link all the bone animation to the mesh
						for(unsigned int i=0;i<animationPtr->boneAnimationCount;i++)
							animationBoneHierarchyConnector[i]=skinPtr->findHierarchyBone(animationPtr->boneAnimations[i].name);

						//copy the transformation matrices
						for(unsigned int i=0;i<skinPtr->boneHierarchyCount;i++)
							transformationMatrices[i]=skinPtr->bonesHierarchy[i].transformationMatrix;
					}
	
					//arranges mesh into groups
					computeFaceGroups(MAXIMUM_MATRIX_COUNT,MAXIMUM_BONE_PER_VERTEX_INFLUENCE_COUNT);
				}

				//updates instance
				void update(const float &dt)
				{
					if(!skinPtr)
						return;

					timePassed+=MIN((1/60.0f),dt);
	
					float currTick=timePassed*animationPtr->ticksPerSecond;
					for(unsigned int j=0;j<animationPtr->boneAnimationCount;j++)
					{
						unsigned int &currBoneHierarchyIndex=animationBoneHierarchyConnector[j];
						//skin::boneHierarchy &currBoneHierarchy=skinPtr->bonesHierarchy[currBoneHierarchyIndex];
		
						//theree transformations
						floatQuaternion interpRotation;
						float3 interpScale;
						float3 interpTranslation;

						//compute rotation
						bool dataAdded=false;
						for(;rotationKeyIndices[currBoneHierarchyIndex]+1<animationPtr->boneAnimations[j].rotationCount;rotationKeyIndices[currBoneHierarchyIndex]++)
						{
							if(currTick<animationPtr->boneAnimations[j].rotations[rotationKeyIndices[currBoneHierarchyIndex]+1].time)
							{
								unsigned int posA=rotationKeyIndices[currBoneHierarchyIndex];
								unsigned int posB=rotationKeyIndices[currBoneHierarchyIndex]+1;
								float w=(currTick-animationPtr->boneAnimations[j].rotations[posA].time)/(animationPtr->boneAnimations[j].rotations[posB].time-animationPtr->boneAnimations[j].rotations[posA].time);
								interpRotation=slerp(animationPtr->boneAnimations[j].rotations[posA].value,animationPtr->boneAnimations[j].rotations[posB].value,w);
								dataAdded=true;
								break;
							}
						}
						if(!dataAdded)
							interpRotation=animationPtr->boneAnimations[j].rotations[rotationKeyIndices[currBoneHierarchyIndex]].value;

						//compute scale
						dataAdded=false;
						for(;scaleKeyIndices[currBoneHierarchyIndex]+1<animationPtr->boneAnimations[j].scaleCount;scaleKeyIndices[currBoneHierarchyIndex]++)
						{
							if(currTick<animationPtr->boneAnimations[j].scales[scaleKeyIndices[currBoneHierarchyIndex]+1].time)
							{
								unsigned int posA=scaleKeyIndices[currBoneHierarchyIndex];
								unsigned int posB=scaleKeyIndices[currBoneHierarchyIndex]+1;
								float w=(currTick-animationPtr->boneAnimations[j].scales[posA].time)/(animationPtr->boneAnimations[j].scales[posB].time-animationPtr->boneAnimations[j].scales[posA].time);
								interpScale=lerp(animationPtr->boneAnimations[j].scales[posA].value,animationPtr->boneAnimations[j].scales[posB].value,w);
								dataAdded=true;
								break;
							}
						}
						if(!dataAdded)
							interpScale=animationPtr->boneAnimations[j].scales[scaleKeyIndices[currBoneHierarchyIndex]].value;

						//compute translation
						dataAdded=false;
						for(;translationKeyIndices[currBoneHierarchyIndex]+1<animationPtr->boneAnimations[j].translationCount;translationKeyIndices[currBoneHierarchyIndex]++)
						{
							if(currTick<animationPtr->boneAnimations[j].translations[translationKeyIndices[currBoneHierarchyIndex]+1].time)
							{
								unsigned int posA=translationKeyIndices[currBoneHierarchyIndex];
								unsigned int posB=translationKeyIndices[currBoneHierarchyIndex]+1;
								float w=(currTick-animationPtr->boneAnimations[j].translations[posA].time)/(animationPtr->boneAnimations[j].translations[posB].time-animationPtr->boneAnimations[j].translations[posA].time);
								interpTranslation=lerp(animationPtr->boneAnimations[j].translations[posA].value,animationPtr->boneAnimations[j].translations[posB].value,w);
								dataAdded=true;
								break;
							}
						}
						if(!dataAdded)
							interpTranslation=animationPtr->boneAnimations[j].translations[translationKeyIndices[currBoneHierarchyIndex]].value;			
		
						////convert into matrix
						//float4x4 rotationMatrix=interpRotation.matrix();
						//float4x4 scaleMatrix=scale(interpScale);
						//float4x4 translationMatrix=translate(interpTranslation);
						////compute transformation matrix
						//transformationMatrices[currBoneHierarchyIndex]=(transpose(rotationMatrix)*transpose(scaleMatrix)*transpose(translationMatrix));
						transformationMatrices[currBoneHierarchyIndex]=transpose((translate(interpTranslation))*(scale(interpScale))*(interpRotation.matrix()));
					}

					//traverses breadth first
					if(skinPtr->rootIndex!=(unsigned int)-1)
						updateHierarchy(skinPtr->bonesHierarchy,skinPtr->rootIndex,&translationMatrix);//traverses breadth first

					//update the final matrix
					for(unsigned int j=0;j<skinPtr->boneHierarchyCount;j++)
					{
						skinData::boneHierarchyData &currBoneHierarchy=skinPtr->bonesHierarchy[j];
						if(currBoneHierarchy.boneIndex==(unsigned int)-1)
							continue;
						skinData::boneData &currBone=skinPtr->bones[currBoneHierarchy.boneIndex];
		
						finalMatrices[j]=currBone.offsetMatrix*combinedTransformationMatrices[j];
					}
				}

				//shows the instance
				void show(graphicsUtility &glu, const camera &eye,const bool &useTexture)
				{	
					bucketList<graphicsUtility::vertexPNT> vertexData(1024);
					
					graphicsUtility::light lightData;
					memset(&lightData,0,sizeof(graphicsUtility::light));
					lightData.position=float3(10,10,0);
					lightData.direction=normalize(float3(0,0,0)-lightData.position);
					lightData.color=float3(1,1,1);

					float4x4 worldMatrix;
					worldMatrix.identity();
	
					float4 color(1.0f,1.0f,1.0f,1.0f);

					//show skinned mesh
					if(skinPtr)
					{
						//show all the groups
						for(unsigned int i=0;i<faceGroups.size();i++)
						{
							//get the current face group
							faceGroupData &currFaceGroup=faceGroups[i];

							for(unsigned int j=0;j<currFaceGroup.faceIndexCount;j++)
							{
								//get current face
								unsigned int &currFaceIndex=currFaceGroup.faceIndices[j];
								modelQuick::meshData::faceData &currFace=meshPtr->faces[currFaceIndex];
					
								for(unsigned int l=0;l<3;l++)
								{
									unsigned int &currVertexIndex=currFace.vertexIndex[l];
									modelQuick::meshData::vertexData &currVert=meshPtr->vertices[currVertexIndex];

									const float2 &texCoord=currVert.texCoord;
									float3 normal=currVert.normal;
									float4 position(currVert.position.x,currVert.position.y,currVert.position.z,1);
									float4 finalPosition;
									finalPosition.clear();

									for(unsigned int m=0;m<MAXIMUM_BONE_PER_VERTEX_INFLUENCE_COUNT;m++)
									{
										unsigned int &currBoneIndicesPerVertex=boneIndicesPerVertex[currVertexIndex*MAXIMUM_BONE_PER_VERTEX_INFLUENCE_COUNT+m];
										float &currBoneWeightsPerVertex=boneWeightsPerVertex[currVertexIndex*MAXIMUM_BONE_PER_VERTEX_INFLUENCE_COUNT+m];
										skinData::boneData &currBone=skinPtr->bones[currBoneIndicesPerVertex];
										unsigned int currBoneHierarchyIndex=currBone.boneHierarchyIndex;
										finalPosition+=transpose(finalMatrices[currBoneHierarchyIndex])*position*currBoneWeightsPerVertex;
									}

									finalPosition.x/=finalPosition.w;
									finalPosition.y/=finalPosition.w;
									finalPosition.z/=finalPosition.w;
					
									//add the vertex data
									vertexData.addBack(graphicsUtility::vertexPNT(finalPosition,normal,texCoord));
								}
							}

							//activate current material
							if(useTexture)
							{
								unsigned int &currMaterialIndex=currFaceGroup.materialIndex;
								//draw
								glu.drawColorNormalTexture(glu.getDeviceContext(),vertexData, *meshPtr->materials[currMaterialIndex].textureSRV, *meshPtr->materials[currMaterialIndex].textureSampler,graphicsDefinitions::PRIMITIVE_TOPOLOGY_TRIANGLELIST,worldMatrix,eye.getViewMatrix(),eye.getProjectionMatrix(),color,lightData);
							}

							//clear the list
							vertexData.clear();

						}
					}
					else
					{
						for(unsigned int j=0;j<meshPtr->faceCount;j++)
						{
							modelQuick::meshData::vertexData &vertA=meshPtr->vertices[meshPtr->faces[j].vertexIndex[0]];
							modelQuick::meshData::vertexData &vertB=meshPtr->vertices[meshPtr->faces[j].vertexIndex[1]];
							modelQuick::meshData::vertexData &vertC=meshPtr->vertices[meshPtr->faces[j].vertexIndex[2]];

							//add the vertex data
							vertexData.addBack(graphicsUtility::vertexPNT(vertA.position,vertA.normal,vertA.texCoord));
							vertexData.addBack(graphicsUtility::vertexPNT(vertB.position,vertB.normal,vertB.texCoord));
							vertexData.addBack(graphicsUtility::vertexPNT(vertC.position,vertC.normal,vertC.texCoord));

							//activate current material
							if(useTexture)
							{
								unsigned int &currMaterialIndex=meshPtr->faces[j].materialIndex;
								//draw
								glu.drawColorNormalTexture(glu.getDeviceContext(),vertexData, *meshPtr->materials[currMaterialIndex].textureSRV, *meshPtr->materials[currMaterialIndex].textureSampler,graphicsDefinitions::PRIMITIVE_TOPOLOGY_TRIANGLELIST,worldMatrix,eye.getViewMatrix(),eye.getProjectionMatrix(),color,lightData);
							}

							//clear the list
							vertexData.clear();
						}
					}
				}

				
				void clear(void)
				{
					delete[] boneIndicesPerVertex;
					delete[] boneWeightsPerVertex;
					delete[] animationBoneHierarchyConnector;
					delete[] transformationMatrices;
					delete[] combinedTransformationMatrices;
					delete[] finalMatrices;
					delete[] rotationKeyIndices;
					delete[] translationKeyIndices;
					delete[] scaleKeyIndices;

					boneIndicesPerVertex=NULL;
					boneWeightsPerVertex=NULL;
					animationBoneHierarchyConnector=NULL;
					transformationMatrices=NULL;
					combinedTransformationMatrices=NULL;
					finalMatrices=NULL;
					rotationKeyIndices=NULL;
					translationKeyIndices=NULL;
					scaleKeyIndices=NULL;

					timePassed=0;					

					faceGroups.clear();
				}

				~instanceData()
				{
					clear();
				}
		};

		//data for the static structure
		struct meshHeader
		{
			//number of meshes
			unsigned int meshCount;
			//number of animations
			unsigned int animationCount;
			//number of skins
			unsigned int skinCount;		
		
			//all the meshes
			union
			{
				meshData *meshes;
				UINT64 _forceSpace64_0;			//Force the union to 64bits. DX SDK trick
			};
			//animations
			union
			{
				animationData *animations;
				UINT64 _forceSpace64_1;			//Force the union to 64bits. DX SDK trick
			};
			//skins
			union
			{
				skinData *skins;
				UINT64 _forceSpace64_2;			//Force the union to 64bits. DX SDK trick
			};	

		} *staticMeshHeader;

	private:
		
		//memory where all the static mesh data is saved
		unsigned char *staticMeshData;
		//length
		unsigned staticMeshDataLength;

		//different instances of the mesh
		bucketList<instanceData> instances;

		//converters memory address to offset
		void convertMemoryAddressToOffset(void);

		//converters offset to memory address
		void convertOffsetToMemoryAddress(void);

	public:

		//constructor
		modelQuick(void)
		{
			staticMeshData=NULL;
			staticMeshHeader=NULL;
			staticMeshDataLength=NULL;
		};

		//init
		bool init(graphicsUtility &glu);
		//updates the mesh
		void update(const float &dt);
		//show the mesh
		void show(graphicsUtility &glu,const camera &eye,const bool useTexture=true);

		//read the file
		bool read(char *fileName);
		//write the file
		bool write(char *fileName);
		//free the data
		void clear(void)
		{
			instances.clear();

			if(staticMeshData)
			{
				//remove all the allocated textures
				for(unsigned int i=0;i<staticMeshHeader->meshCount;i++)
				{
					meshData &currMesh=staticMeshHeader->meshes[i];
					for(unsigned int j=0;j<currMesh.materialCount;j++)
					{
						meshData::materialData &currMaterial=currMesh.materials[j];
						delete currMaterial.textureSRV;
						delete currMaterial.textureSampler;
					}
				}
				delete[] staticMeshData;
				staticMeshData=NULL;
				staticMeshHeader=NULL;
				staticMeshDataLength=NULL;
			}
		};
		//destructor
		~modelQuick()
		{
			clear();		
		};

		//convert model to modelquick
		modelQuick& operator=(const model& data);
};

#endif
